package 力扣;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * @author yyq
 * @create 2022-04-06 10:30
 * 二叉树的前序遍历
 * 实现方式:
 *          1.递归遍历
 *          2.迭代遍历
 *
 */
public class leetcode144 {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if(root!=null)
        preOrder(list,root);
        return list;
    }

    private void preOrder(List<Integer> list, TreeNode root) {
        if(root==null) return;
        if(root!=null) list.add(root.val);
        if(root.left!=null) preOrder(list,root.left);
        if(root.right!=null) preOrder(list,root.right);
    }
    public List<Integer> preorderIterative(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        Stack<TreeNode> stack=new Stack<>();
        if(root!=null) stack.push(root);
        else return list;
        while (!stack.isEmpty()){
            TreeNode pop = stack.pop();
            list.add(pop.val);
            if(pop.right!=null)
            stack.push(pop.right);
            if(pop.left!=null)
            stack.push(pop.left);
        }
        return list;

    }
}
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
         this.right = right;
     }
  }
